Threaded Binary Tree

线索二叉树的定义、实现、三种线索化方式以及其对应的遍历方式。

#include <iostream>
using namespace std;
typedef struct BiThrNode {//线索二叉树的结点
	int data;//数据域
	BiThrNode *lchild, *rchild;//左右孩子指针
	BiThrNode *parent;
	int LTag = 0, RTag = 0;//左右标志
}BiThrNode, *BiThrTree;

class ThreadBiTree {
private:
	BiThrNode *bt;//根结点
	BiThrNode *pre;
	void RCreate(BiThrNode *p, int k, int end);
public:
	BiThrNode *Thrt;//头结点
	ThreadBiTree() { bt = NULL; pre = NULL; Thrt = new BiThrNode; }//构造函数，对二叉链表进行初始化
	void CreateBiTree(int end);
	BiThrNode *Getroot();//二叉树不为空获取根结点指针，否则返回NULL
	void BiTreeDisplay(BiThrNode *bt, int level);//二叉树的树形显示算法
	void PreThreading(BiThrTree p);//先序线索化递归函数
	int PreOrderThreading(BiThrTree &Thrt, BiThrTree T);//先序遍历进行先序线索化
	int PreOrderTraverse_Thr(BiThrTree T);//先序遍历线索二叉树的非递归算法
	void InThreading(BiThrTree p);//中序线索化递归函数
	int InOrderThreading(BiThrTree &Thrt, BiThrTree T);//中序遍历进行中序线索化
	int InOrderTraverse_Thr(BiThrTree T);//中序遍历线索二叉树的非递归算法
	void PostThreading(BiThrTree p);//后序线索化递归函数
	int PostOrderTraverse_Thr(BiThrTree T);//后序遍历线索二叉树的非递归算法
};

void ThreadBiTree::RCreate(BiThrNode * p, int k, int end) {
	BiThrNode *q;
	int e;
	cin >> e;
	if (e != end) {
		q = new BiThrNode;
		q->data = e;
		q->lchild = NULL;
		q->rchild = NULL;
		q->parent = p;
		if (k == 1) p->lchild = q;
		if (k == 2) p->rchild = q;
		RCreate(q, 1, end);
		RCreate(q, 2, end);
	}
}

void ThreadBiTree::CreateBiTree(int end) {
	cout << "请按先序序列的顺序输入二叉树，0为空指针域标志：" << endl;
	BiThrNode *p;
	int e;
	cin >> e;
	if (e == end) return;
	p = new BiThrNode;
	if (!p) {
		cout << "申请内存失败！" << endl;
		exit(-1);
	}
	p->data = e;
	p->lchild = NULL;
	p->rchild = NULL;
	bt = p;
	RCreate(p, 1, end);
	RCreate(p, 2, end);
}

BiThrNode * ThreadBiTree::Getroot() {
	if (bt != NULL) return bt;
	return NULL;
}



void ThreadBiTree::BiTreeDisplay(BiThrNode * bt, int level) {
	if (bt) {
		BiTreeDisplay(bt->rchild, level + 1);
		for (int i = 0; i < level; i++) cout << "  ";
		cout << bt->data << endl;
		BiTreeDisplay(bt->lchild, level + 1);
	}
}

void ThreadBiTree::PreThreading(BiThrTree p) {
	if (p) {
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (pre != NULL && !pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
		if (p->LTag == 0) PreThreading(p->lchild);
		if (p->RTag == 0) PreThreading(p->rchild);
	}
}

int ThreadBiTree::PreOrderThreading(BiThrTree & Thrt, BiThrTree T) {
	Thrt->LTag = 0; Thrt->RTag = 1;
	Thrt->rchild = Thrt;
	if (!T) Thrt->lchild = Thrt;
	else {
		Thrt->lchild = T; pre = Thrt;
		PreThreading(T);
		pre->rchild = Thrt; pre->RTag = 1;
		Thrt->rchild = pre;
	}
	return 1;
}

int ThreadBiTree::PreOrderTraverse_Thr(BiThrTree T) {
	BiThrNode *p;
	p = T->lchild;
	while (p != T) {
		while (p->lchild != NULL && p->LTag == 0) {
			cout << p->data << " ";
			p = p->lchild;
		}
		cout << p->data << " ";
		if (p->LTag == 1) p = p->rchild;
	}
	return 1;
}

void ThreadBiTree::InThreading(BiThrTree p) {
	if (p) {
		InThreading(p->lchild);
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (!pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
		InThreading(p->rchild);
	}
}

int ThreadBiTree::InOrderThreading(BiThrTree & Thrt, BiThrTree T) {
	Thrt->LTag = 0; Thrt->RTag = 1;//Thrt指向头结点
	Thrt->rchild = Thrt;
	if (!T) Thrt->lchild = Thrt;
	else {
		Thrt->lchild = T; pre = Thrt;
		InThreading(T);
		pre->rchild = Thrt; pre->RTag = 1;
		Thrt->rchild = pre;
	}
	return 1;
}

int ThreadBiTree::InOrderTraverse_Thr(BiThrTree T) {
	BiThrNode *p;
	p = T->lchild;
	while (p != T) {
		while (p->LTag == 0) p = p->lchild;
		cout << p->data << " ";
		while (p->RTag == 1 && p->rchild != T) {
			p = p->rchild;
			cout << p->data << " ";
		}
		p = p->rchild;
	}
	return 1;
}

void ThreadBiTree::PostThreading(BiThrTree p) {
	if (p) {
		PostThreading(p->lchild);
		PostThreading(p->rchild);
		if (!p->lchild) p->LTag = 1, p->lchild = pre;
		if (pre && !pre->rchild) pre->RTag = 1, pre->rchild = p;
		pre = p;
	}
}

int ThreadBiTree::PostOrderTraverse_Thr(BiThrTree T) {
	if (T) {
		BiThrTree p = T;
		pre = NULL;
		while (pre != T) {
			while (p->LTag == 0) p = p->lchild;
			while (p&&p->RTag == 1) {
				cout << p->data << " ";
				pre = p;
				p = p->rchild;
			}
			while (pre != T && p->rchild == pre) {
				cout << p->data << " ";
				pre = p;
				if (pre != T)p = p->parent;
			}
			if (p->RTag == 0)p = p->rchild;
		}
	}
	return 1;
}

int main() {
	ThreadBiTree TA;
	TA.CreateBiTree(0);
	TA.BiTreeDisplay(TA.Getroot(), 0);
	TA.PreOrderThreading(TA.Thrt, TA.Getroot());
	cout << "先序遍历先序线索二叉树：";
	TA.PreOrderTraverse_Thr(TA.Thrt);
	cout << endl;
	ThreadBiTree TB;
	TB.CreateBiTree(0);
	TB.BiTreeDisplay(TB.Getroot(), 0);
	TB.InOrderThreading(TB.Thrt, TB.Getroot());
	cout << "中序遍历中序线索二叉树：";
	TB.InOrderTraverse_Thr(TB.Thrt);
	cout << endl;
	ThreadBiTree TC;
	TC.CreateBiTree(0);
	TC.BiTreeDisplay(TC.Getroot(), 0);
	TC.PostThreading(TC.Getroot());
	cout << "后序遍历后序线索二叉树：";
	TC.PostOrderTraverse_Thr(TC.Getroot());
	cout << endl;
	return 0;
}